/*
 * @lc app=leetcode.cn id=416 lang=javascript
 *
 * [416] 分割等和子集
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canPartition = function (nums) {
  let sum = nums.reduce((a,b)=>a+b)
  let target = sum /2;
  if (~~target !== target) return false;
  nums.sort((a,b)=>a-b)
//   function help(nums, target) {
//     let l = 0;
//     let r = nums.length - 1;
//     let mid = (l + r) >> 1;
//     while (l < r) {
//       if (nums[mid] === target) return mid;
//       if (nums[mid] > target) {
//         r = mid;
//       } else {
//         l = mid + 1;
//       }
//       mid = (l + r) >> 1;
//     }
//     return r - 1;
//   }
//   let index = help(nums, target);
//   if (nums[index] === target) return true;
  let db=[[0,nums[0]]]
  for(let i=1;i<nums.length;i++){
      db[i]=[]
      let set=new Set()
      for(let item of db[i-1]){
        if(item===target)return true
        if(item+nums[i]==target)return true
        if(item<target&&!set.has(item)){
          db[i].push(item)
          set.add(item)
        }
        if(item+nums[i]<target&&!set.has(item+nums[i])){
          db[i].push(item+nums[i])
          set.add(item+nums[i])
        }
      }
      db[i]=[...set]
  }
  return false
};
// @lc code=end
canPartition([14,9,8,4,3,2])